#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>

int getEntry(int a[], int size, int index)
{
  if (index < 0) return INT_MIN;
  else if (index >= size) return INT_MAX;
  else return a[index];
}

int findKthSmallest(int A[], int m, int B[], int n, int k)
{
  assert(m >= 0);
  assert(n >= 0);
  assert(k > 0);
  assert(k <= m + n);
  printf("m = %d, n = %d\n", m, n);

  //int i = (int)((double)m / (m + n) * (k - 1)), j = k - i - 1;
  int i, j;
  if ((k - m/2 - 1) < 0) 

#if 0
  int Ai_1 = (i < 1) ? INT_MIN : A[i - 1];
  int Ai   = (i >= m) ? INT_MAX : A[i];
  int Bj_1 = (j < 1) ? INT_MIN : B[j - 1];
  int Bj   = (j >= n) ? INT_MAX : B[j];
#endif
  int Ai_1 = getEntry(A, m, i - 1);
  int Ai   = getEntry(A, m, i);
  int Bj_1 = getEntry(B, n, j - 1);
  int Bj   = getEntry(B, n, j);

  if (Bj_1 < Ai && Ai < Bj) {
    return Ai;
  } else if (Ai_1 < Bj && Bj < Ai) {
    return Bj;
  }

  if (Ai < Bj) {
    return findKthSmallest(A + i + 1, m - i - 1, B, n, k - i - 1);
  } else {
    return findKthSmallest(A, m, B + j + 1, n - j - 1, k - j - 1);
  }
}

int main(int argc, char *argv[])
{
  int A[] = {1, 3, 5, 7, 9};
  int B[] = {2, 4, 6};

  int k = atoi(argv[1]);

  int ret = findKthSmallest(A, sizeof(A) / sizeof(int),
                            B, sizeof(B) / sizeof(int),
                            k);


  printf("%d th smallest element: %d\n", k, ret);
}
